/*
 * @Author: szx
 * @Date: 2022-02-04 14:18:32
 * @LastEditTime: 2022-02-04 20:28:15
 * @Description:
 * @FilePath: \leetcode\900-999\912\912_fast_sort.js
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */

// 快速排序
// var sortArray = function (nums) {
//     return quickSort(nums, 0, nums.length - 1);
// };

// 快排
// function quickSort(nums, left, right) {
//     if (left < right) {
//         // 划分的边界线
//         let partitionIndex = partition(nums, left, right);
//         quickSort(nums, left, partitionIndex - 1);
//         quickSort(nums, partitionIndex + 1, right);
//     }
//     return nums;
// }

// function partition(nums, left, right) {
//     // 分区操作
//     var pivot = left, // 设定基准值（pivot）
//         index = pivot + 1;
//     for (var i = index; i <= right; i++) {
//         if (nums[i] < nums[pivot]) {
//             swap(nums, i, index);
//             index++;
//         }
//     }
//     swap(nums, pivot, index - 1);
//     return index - 1;
// }

// function swap(nums, i, j) {
//     var temp = nums[i];
//     nums[i] = nums[j];
//     nums[j] = temp;
// }

// 最基础版本的快速排序
// var sortArray = function (nums) {
//     return quickSort(nums, 0, nums.length - 1);
// };

// // 快速排序，找到pivot之后，分别排左边和右边
// function quickSort(nums, low, high) {
//     if (low < high) {
//         let pivot = partition(nums, low, high);
//         quickSort(nums, low, pivot - 1);
//         quickSort(nums, pivot + 1, high);
//     }
//     return nums;
// }

// //分治递归
// function partition(nums, begin, end) {
// 	let pivotIndex = begin;
// 	let pivot = nums[pivotIndex];
// 	swap(nums, pivotIndex, end);

// 	let low = begin;
// 	let high = end;

// 	while (low < high) {
// 		// 因为把pivot放在了最后，所以low指针先走
// 		while (low < high && nums[low] < pivot) low++;
// 		while (low < high && nums[high] > pivot) high--;
// 		if(low < high) swap(nums, low, high);
// 	}

// 	swap(nums, low, end);
// 	return low;
// }

// function swap(nums, i, j) {
//     let temp = nums[i];
//     nums[i] = nums[j];
//     nums[j] = temp;
// }

// const sortArray = (nums) => {
//     const sort = (arr, left = 0, right = arr.length - 1) => {
//         if (left >= right) {
//             //如果左边的索引大于等于右边的索引说明整理完毕
//             return;
//         }
//         let i = left;
//         let j = right;
//         const baseVal = arr[j]; // 取无序数组最后一个数为基准值
//         while (i < j) {
//             //把所有比基准值小的数放在左边，大的数放在右边
//             while (i < j && arr[i] <= baseVal) {
//                 //找到一个比基准值大的数交换
//                 i++;
//             }
//             arr[j] = arr[i]; // 将较大的值放在右边，如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
//             while (j > i && arr[j] >= baseVal) {
//                 //找到一个比基准值小的数交换
//                 j--;
//             }
//             arr[i] = arr[j]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
//         }
//         arr[j] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）

//         sort(arr, left, j - 1); // 将左边的无序数组重复上面的操作
//         sort(arr, j + 1, right); // 将右边的无序数组重复上面的操作
//     };
//     sort(nums);
//     return nums;
// };

// const sortArray = (nums) => {
//     const sort = (arr, left = 0, right = arr.length - 1) => {
//         if (left >= right) {
//             //如果左边的索引大于等于右边的索引说明整理完毕
//             return;
//         }
//         let i = left;
//         let j = right;
//         let baseVal = Math.floor(Math.random() * (right - left + 1)) + left;
//         [nums[j], nums[baseVal]] = [nums[baseVal], nums[j]];
//         baseVal = nums[j];
//         // const baseVal = arr[j]; // 取无序数组最后一个数为基准值
//         while (i < j) {
//             //把所有比基准值小的数放在左边，大的数放在右边
//             while (i < j && arr[i] <= baseVal) {
//                 //找到一个比基准值大的数交换
//                 i++;
//             }
//             arr[j] = arr[i]; // 将较大的值放在右边，如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
//             while (j > i && arr[j] >= baseVal) {
//                 //找到一个比基准值小的数交换
//                 j--;
//             }
//             arr[i] = arr[j]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
//         }
//         arr[j] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
//         sort(arr, left, j - 1); // 将左边的无序数组重复上面的操作
//         sort(arr, j + 1, right); // 将右边的无序数组重复上面的操作
//     };

//     sort(nums);
//     return nums;
// };

const sortArray = (nums) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if (left >= right) {
            //如果左边的索引大于等于右边的索引说明整理完毕
            return;
        }

        let baseIndex = Math.floor(Math.random() * (right - left + 1)) + left;
        // 随机选取left到right中的一个数字，然后和right进行交换
        swap(arr, baseIndex, right);

        // 基准就选取最后一个，也就是之前随机得到的数字
        const pivot = arr[right];
        let i = left; // i是在左边的，j是在右边的
        // 循环从left到right-1，整个过程有点像冒泡（选择？），就是把基准小的都冒泡到左边去
        for (let j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                // 因为j是大于等于i，也就是在i的右边，所以找到比基准小的arr[j]，那么就交换
                swap(arr, i, j);
                i = i + 1;
            }
        }
        // 最后交换i和right位置的数字，此时arr[i]是大于等于基准的值
        swap(arr, i, right);

        sort(arr, left, i - 1); // 将左边的无序数组重复 上面的操作
        sort(arr, i + 1, right); // 将右边的无序数组重复上面的操作
    };
    const swap = (nums, i, j) => {
        const temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    };

    sort(nums);
    return nums;
};

console.log(sortArray([4, 5, 2, 1, 3]));
